1. Field of the Invention
The invention relates to a computer-based IC floorplanner that iteratively partitions IC floorspace into progressively smaller regions, allocating IC modules to regions after each partitioning until the regions are sufficiently small, creates a separate floorplan for each small region, and then iteratively merges and refines floorplans for neighboring regions to obtain a single floorplan for the entire IC floorspace.
2. Description of Related Art
An integrated circuit (IC) designer typically generates a text-based netlist describing an IC as a hierarchy of modules formed by instances of various components (cells) interconnected by signal paths (nets) formed by conductors residing on various horizontal layers of the IC and by conductive “vias” passing vertically between layers. As illustrated in FIG. 1, a netlist is typically hierarchical in nature with cells instances 10 being organized into low level modules 12 and lower level modules being organized into higher level modules 14 and 15. FIG. 1 depicts a simple design having four hierarchal levels 16-19 with varying numbers of cell instances 10 (represented by circles) and modules 14 (represented by squares) at each level. A more complex design will include more cell instances and modular levels. Although an IC may include many modules formed by instances of standard cells such as transistors and logic gates, an IC may also include “intellectual property” (IP) modules implementing large devices such as memories and microprocessors.
After creating the netlist, the designer employs computer-aided placement and routing (P&R) tools to produce an IC layout including a placement plan indicating a position for each component and a routing plan describing the routes and positions of conductors and vias forming the nets. The IC layout guides IC fabrication.
The number of components included in an IC continues to grow dramatically as nanometer IC technologies continue to shrink components, and while modern ICs can include millions of transistors, ICs with billions of transistors are on the horizon. Since the time required for placement and routing tools to generate an IC layout increases with the number of components in the design, using large IP modules in large-scale IC designs can help to reduce the number of components that have to be placed and therefore the time required to generate an IC layout. However large, inflexible IP modules can also make it more difficult for a placement and routing tool to place and route remaining portions of an IC.
A typical P&R tool initially generates an initial floorplan allocating a separate area of an IC's floor space to various modules of an IC and then generates placement and routing plans for each area. Placement and routing is typically an iterative process. After creating a floorplan and then creating a placement plan consistent with the floorplan, a P&R tool attempts to create a routing plan, and if it is unable to develop a suitable routing plan for that placement plan, it will modify the placement plan and again attempt to develop suitable routing plan. If the P&R tool cannot find a suitable placement and routing solution for a given floorplan, it will modify the floorplan and attempt placement and routing again. The ability of a P&R tool to quickly find a suitable layout solution greatly depends on how well the initial floorplan anticipates the floorspace requirements of each IC module and the net routing requirements between the modules.
Floorplanning algorithms continue to evolve to meet the challenges presented constantly increasing design complexity. As illustrated in FIG. 2A, a hierarchical floorplanner partitions the IC floor space into a set of regions 20, each sized and positioned as necessary to accommodate an estimated size of a separate module at a high level of the design hierarchy. For example, since the design of FIG. 1 has seven modules at level 17, a hierarchical floorplanner could estimate the size of each cell instance or module at that level and establish a corresponding region 20 for each module. Sizes and shapes of cells and IP modules are known, and a floorplanning algorithm can estimate the size and shape of an area needed for each custom module based on the known areas of the cells that form it. As illustrated in FIG. 2B, the hierarchal floorplanner then further partitions the region 20 assigned to each custom module into a set of subregions 22, each sized and positioned to accommodate sub modules or cell instances forming that model at a next lower level of the design hierarchy. The subdivision process continues recursively until the IC floorspace has been partitioned into small regions for accommodating modules and cell instances at a desired low level of the design hierarchy. Such a top-down hierarchical floorplanner can quickly and efficiently generate a floorplan providing sufficient space for each cell or module of a large-scale design but will often produce an unroutable placement plan because it does not directly take into account routing requirements between modules when generating a floorplan.
A typical prior art multilevel floorplanning framework as illustrated in FIGS. 3A-3F takes a bottom-up/top-down approach to determining a suitable size, shape, orientation and position for each area of a floorplan. Initially viewing the IC at a low level of the design hierarchy at the start of a “clustering” phase of the process, the floorplanner groups highly interconnected low level modules and cell instances into a set of small clusters and provides a suitably sized region 24 for each cluster (FIG. 3A). As illustrated in FIG. 3B, highly interconnected regions 24 are then merged to form larger regions 25 with the clusters within each larger region 25 arranged to limit the lengths of nets that will interconnect them. The iterative merging process continues in a similar manner to form progressively larger regions 26 (FIG. 3C) until all clusters have been merged and suitably arranged into a single region 27 (FIG. 3D).
At this point the floorplanner begins an iterative declustering process wherein it partitions regions into progressively smaller regions that are rearranged as necessary to best fit within the boundary 29 of the IC placement area. FIG. 3E shows that region 27 of FIG. 3D has been partitioned into a set of smaller regions 28 which have been arranged to fit as closely as possible within placement area boundary 29. FIG. 3F shows the result of partitioning various regions 28 into smaller regions and rearranging them to fit within the placement area boundary 29. The floorplanning process ends when the regions 30 are of a desired small size and fit within the IC placement area boundary 29. The boundaries of regions 30 define the floorplan for subsequent placement and routing processes.
The multilevel floorplanning framework illustrated in FIGS. 3A-3F is known as the “V-Cycle” framework, but it may be more descriptively called a “Λ-shaped” framework since it includes an initial bottom-up clustering phase followed by a top-down declustering phase. A P&R tool employing a Λ-shaped floorplanning framework to produce a floorplan can normally derive a placement plan consistent with the floorplan, but it often fails to produce a suitable routing plan because it fails to find suitable routes for the longer nets. Since the Λ-shaped framework initially operates in a bottom-up manner, clustering and arranging modules based on considerations of shorter nets rather than on longer nets, wrong choices early in the clustering process can make longer nets longer, thereby resulting in a suboptimal the floorplan solution during the declustering process. In order to reduce the likelihood that a floorplan will lead to an unroutable placement plan, it would be helpful to take the longer interconnections between modules into account earlier in the floorplanning process.